home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / facebsp.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  7.1 KB  |  359 lines
  1.  
  2. #include "qbsp.h"
  3.  
  4.  
  5. int            c_faceLeafs;
  6.  
  7.  
  8. /*
  9. ================
  10. AllocBspFace
  11. ================
  12. */
  13. bspface_t    *AllocBspFace( void ) {
  14.     bspface_t    *f;
  15.  
  16.     f = malloc(sizeof(*f));
  17.     memset( f, 0, sizeof(*f) );
  18.  
  19.     return f;
  20. }
  21.  
  22. /*
  23. ================
  24. FreeBspFace
  25. ================
  26. */
  27. void    FreeBspFace( bspface_t *f ) {
  28.     if ( f->w ) {
  29.         FreeWinding( f->w );
  30.     }
  31.     free( f );
  32. }
  33.  
  34.  
  35. /*
  36. ================
  37. SelectSplitPlaneNum
  38. ================
  39. */
  40. int hintsplit;
  41.  
  42. #define    BLOCK_SIZE    1024
  43. int SelectSplitPlaneNum( node_t *node, bspface_t *list ) {
  44.     bspface_t    *split;
  45.     bspface_t    *check;
  46.     bspface_t    *bestSplit;
  47.     int            splits, facing, front, back;
  48.     int            side;
  49.     plane_t        *plane;
  50.     int            value, bestValue;
  51.     int            i;
  52.     vec3_t        normal;
  53.     float        dist;
  54.     int            planenum;
  55.  
  56.     hintsplit = qfalse;
  57.     // if it is crossing a 1k block boundary, force a split
  58.     for ( i = 0 ; i < 2 ; i++ ) {
  59.         dist = BLOCK_SIZE * ( floor( node->mins[i] / BLOCK_SIZE ) + 1 );    
  60.         if ( node->maxs[i] > dist ) {
  61.             VectorClear( normal );
  62.             normal[i] = 1;
  63.             planenum = FindFloatPlane( normal, dist );
  64.             return planenum;
  65.         }
  66.     }
  67.  
  68.     // pick one of the face planes
  69.     bestValue = -99999;
  70.     bestSplit = list;
  71.  
  72.     for ( split = list ; split ; split = split->next ) {
  73.         split->checked = qfalse;
  74.     }
  75.  
  76.     for ( split = list ; split ; split = split->next ) {
  77.         if ( split->checked ) {
  78.             continue;
  79.         }
  80.         plane = &mapplanes[ split->planenum ];
  81.         splits = 0;
  82.         facing = 0;
  83.         front = 0;
  84.         back = 0;
  85.         for ( check = list ; check ; check = check->next ) {
  86.             if ( check->planenum == split->planenum ) {
  87.                 facing++;
  88.                 check->checked = qtrue;    // won't need to test this plane again
  89.                 continue;
  90.             }
  91.             side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
  92.             if ( side == SIDE_CROSS ) {
  93.                 splits++;
  94.             } else if ( side == SIDE_FRONT ) {
  95.                 front++;
  96.             } else if ( side == SIDE_BACK ) {
  97.                 back++;
  98.             }
  99.         }
  100.         value =  5*facing - 5*splits; // - abs(front-back);
  101.         if ( plane->type < 3 ) {
  102.             value+=5;        // axial is better
  103.         }
  104.         value += split->priority;        // prioritize hints higher
  105.  
  106.         if ( value > bestValue ) {
  107.             bestValue = value;
  108.             bestSplit = split;
  109.         }
  110.     }
  111.  
  112.     if ( bestValue == -99999 ) {
  113.         return -1;
  114.     }
  115.  
  116.     if (bestSplit->hint)
  117.         hintsplit = qtrue;
  118.  
  119.     return bestSplit->planenum;
  120. }
  121.  
  122. int    CountFaceList( bspface_t *list ) {
  123.     int        c;
  124.     c = 0;
  125.     for ( ; list ; list = list->next ) {
  126.         c++;
  127.     }
  128.     return c;
  129. }
  130.  
  131. /*
  132. ================
  133. BuildFaceTree_r
  134. ================
  135. */
  136. void    BuildFaceTree_r( node_t *node, bspface_t *list ) {
  137.     bspface_t    *split;
  138.     bspface_t    *next;
  139.     int            side;
  140.     plane_t        *plane;
  141.     bspface_t    *newFace;
  142.     bspface_t    *childLists[2];
  143.     winding_t    *frontWinding, *backWinding;
  144.     int            i;
  145.     int            splitPlaneNum;
  146.  
  147.     i = CountFaceList( list );
  148.  
  149.     splitPlaneNum = SelectSplitPlaneNum( node, list );
  150.     // if we don't have any more faces, this is a node
  151.     if ( splitPlaneNum == -1 ) {
  152.         node->planenum = PLANENUM_LEAF;
  153.         c_faceLeafs++;
  154.         return;
  155.     }
  156.  
  157.     // partition the list
  158.     node->planenum = splitPlaneNum;
  159.     node->hint = hintsplit;
  160.     plane = &mapplanes[ splitPlaneNum ];
  161.     childLists[0] = NULL;
  162.     childLists[1] = NULL;
  163.     for ( split = list ; split ; split = next ) {
  164.         next = split->next;
  165.  
  166.         if ( split->planenum == node->planenum ) {
  167.             FreeBspFace( split );
  168.             continue;
  169.         }
  170.  
  171.         side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
  172.  
  173.         if ( side == SIDE_CROSS ) {
  174.             ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
  175.                 &frontWinding, &backWinding );
  176.             if ( frontWinding ) {
  177.                 newFace = AllocBspFace();
  178.                 newFace->w = frontWinding;
  179.                 newFace->next = childLists[0];
  180.                 newFace->planenum = split->planenum;
  181.                 newFace->priority = split->priority;
  182.                 newFace->hint = split->hint;
  183.                 childLists[0] = newFace;
  184.             }
  185.             if ( backWinding ) {
  186.                 newFace = AllocBspFace();
  187.                 newFace->w = backWinding;
  188.                 newFace->next = childLists[1];
  189.                 newFace->planenum = split->planenum;
  190.                 newFace->priority = split->priority;
  191.                 newFace->hint = split->hint;
  192.                 childLists[1] = newFace;
  193.             }
  194.             FreeBspFace( split );
  195.         } else if ( side == SIDE_FRONT ) {
  196.             split->next = childLists[0];
  197.             childLists[0] = split;
  198.         } else if ( side == SIDE_BACK ) {
  199.             split->next = childLists[1];
  200.             childLists[1] = split;
  201.         }
  202.     }
  203.  
  204.  
  205.     // recursively process children
  206.     for ( i = 0 ; i < 2 ; i++ ) {
  207.         node->children[i] = AllocNode();
  208.         node->children[i]->parent = node;
  209.         VectorCopy( node->mins, node->children[i]->mins );
  210.         VectorCopy( node->maxs, node->children[i]->maxs );
  211.     }
  212.  
  213.     for ( i = 0 ; i < 3 ; i++ ) {
  214.         if ( plane->normal[i] == 1 ) {
  215.             node->children[0]->mins[i] = plane->dist;
  216.             node->children[1]->maxs[i] = plane->dist;
  217.             break;
  218.         }
  219.     }
  220.  
  221.     for ( i = 0 ; i < 2 ; i++ ) {
  222.         BuildFaceTree_r ( node->children[i], childLists[i]);
  223.     }
  224. }
  225.  
  226.  
  227. /*
  228. ================
  229. FaceBSP
  230.  
  231. List will be freed before returning
  232. ================
  233. */
  234. tree_t *FaceBSP( bspface_t *list ) {
  235.     tree_t        *tree;
  236.     bspface_t    *face;
  237.     int            i;
  238.     int            count;
  239.  
  240.     qprintf( "--- FaceBSP ---\n" );
  241.  
  242.     tree = AllocTree ();
  243.  
  244.     count = 0;
  245.     for ( face = list ; face ; face = face->next ) {
  246.         count++;
  247.         for ( i = 0 ; i < face->w->numpoints ; i++ ) {
  248.             AddPointToBounds( face->w->p[i], tree->mins, tree->maxs);
  249.         }
  250.     }
  251.     qprintf( "%5i faces\n", count );
  252.  
  253.     tree->headnode = AllocNode();
  254.     VectorCopy( tree->mins, tree->headnode->mins );
  255.     VectorCopy( tree->maxs, tree->headnode->maxs );
  256.     c_faceLeafs = 0;
  257.  
  258.     BuildFaceTree_r ( tree->headnode, list );
  259.  
  260.     qprintf( "%5i leafs\n", c_faceLeafs );
  261.  
  262.     return tree;
  263. }
  264.  
  265.  
  266. /*
  267. =================
  268. BspFaceForPortal
  269. =================
  270. */
  271. bspface_t *BspFaceForPortal( portal_t *p ) {
  272.     bspface_t    *f;
  273.  
  274.     f = AllocBspFace();
  275.     f->w = CopyWinding( p->winding );
  276.     f->planenum = p->onnode->planenum & ~1;
  277.  
  278.     return f;
  279. }
  280.  
  281.  
  282.  
  283. /*
  284. =================
  285. MakeStructuralBspFaceList
  286. =================
  287. */
  288. bspface_t    *MakeStructuralBspFaceList( bspbrush_t *list ) {
  289.     bspbrush_t    *b;
  290.     int            i;
  291.     side_t        *s;
  292.     winding_t    *w;
  293.     bspface_t    *f, *flist;
  294.  
  295.     flist = NULL;
  296.     for ( b = list ; b ; b = b->next ) {
  297.         if ( b->detail ) {
  298.             continue;
  299.         }
  300.         for ( i = 0 ; i < b->numsides ; i++ ) {
  301.             s = &b->sides[i];
  302.             w = s->winding;
  303.             if ( !w ) {
  304.                 continue;
  305.             }
  306.             f = AllocBspFace();
  307.             f->w = CopyWinding( w );
  308.             f->planenum = s->planenum & ~1;
  309.             f->next = flist;
  310.             if (s->surfaceFlags & SURF_HINT) {
  311.                 //f->priority = HINT_PRIORITY;
  312.                 f->hint = qtrue;
  313.             }
  314.             flist = f;
  315.         }
  316.     }
  317.  
  318.     return flist;
  319. }
  320.  
  321. /*
  322. =================
  323. MakeVisibleBspFaceList
  324. =================
  325. */
  326. bspface_t    *MakeVisibleBspFaceList( bspbrush_t *list ) {
  327.     bspbrush_t    *b;
  328.     int            i;
  329.     side_t        *s;
  330.     winding_t    *w;
  331.     bspface_t    *f, *flist;
  332.  
  333.     flist = NULL;
  334.     for ( b = list ; b ; b = b->next ) {
  335.         if ( b->detail ) {
  336.             continue;
  337.         }
  338.         for ( i = 0 ; i < b->numsides ; i++ ) {
  339.             s = &b->sides[i];
  340.             w = s->visibleHull;
  341.             if ( !w ) {
  342.                 continue;
  343.             }
  344.             f = AllocBspFace();
  345.             f->w = CopyWinding( w );
  346.             f->planenum = s->planenum & ~1;
  347.             f->next = flist;
  348.             if (s->surfaceFlags & SURF_HINT) {
  349.                 //f->priority = HINT_PRIORITY;
  350.                 f->hint = qtrue;
  351.             }
  352.             flist = f;
  353.         }
  354.     }
  355.  
  356.     return flist;
  357. }
  358.  
  359.